package countQuadruplets;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int countQuadruplets(int[] nums) {
//        int m = nums.length;
//        int ans = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = i+1; j < m; j++) {
//                for (int k = j+1; k < m; k++) {
//                    for (int l = k+1; l < m; l++) {
//                        if(nums[i] + nums[j] + nums[k] == nums[l]) {
//                            ans++;
//                        }
//                    }
//                }
//            }
//        }
//        return ans;
//        int ans = 0;
//        Map<Integer,Integer> map = new HashMap<>();
//        int n = nums.length;
//        for (int c = n-2; c >=2 ; --c) {
//            map.put(nums[c+1],map.getOrDefault(nums[c+1],0)+1);
//            for (int a = 0; a < c; a++) {
//                for (int b = a+1; b < c; b++) {
//                    ans+=map.getOrDefault(nums[a] + nums[b] + nums[c],0);
//                }
//            }
//        }
//        return ans;

        // 使用 hash 表存储 nums[a] + nums[b] == nums[d] - nums[c]
        // 存储 nums[d] - nums[c]
//        int n = nums.length;
//        Map<Integer,Integer> map = new HashMap<>();
//        int ans = 0;
//        for (int b = n-3; b >=1 ; b--) {
//            // 存放nums[d] - nums[c]的值
//            for (int d = b + 2; d <n ; ++d) {
//                int t = nums[d] - nums[b+1];
//                map.put(t,map.getOrDefault(t,0)+1);
//            }
//            for (int a = 0; a < b; a++) {
//                ans+= map.getOrDefault(nums[a] + nums[b],0);
//            }
//        }
//        return ans;

        // 背包求解
        // dp[i][j][k] 表示从前i个数字中选择j个数字和等于k
        // 每个数字可以选也可以不选 dp[i][j][k] = dp[i-1][j-1][k-nums[i-1]](选) + dp[i-1][j][k](不选).
        // dp[0][0][0] = 1;
        int [][]dp = new int[4][101];
        dp[0][0] = 1;
        int ans = 0;
        for (int num: nums) {
            for (int j = 3; j >= 0; j--) {
                for (int i = num; i <dp[0].length; i++) {
                    dp[j][i] += dp[j-1][i-num];
                }
            }
            ans += dp[3][num];
        }
        return ans;
    }
}
